#include <iostream>
// #include "insertionSort2.h"

using namespace std;

// 将arr[l...mid]和arr[mid+1...r]两部分进行归并
template<typename T>
void __merge(T arr[], int l, int mid, int r){
	T aux[r - l + 1];	// 辅助空间和 要合并两部分一样大
	for(int i = l; i <= r; ++i)
		aux[i - l] = arr[i];		//  l 的偏移量

	// 定义两个指针分别指向 两个排好序部分
	int i = l, j = mid + 1;
	for(int k = l;k <= r; ++k){		// l-r 使用k 索引遍历,决定arr[k]位置
		if(i > mid){				// 右侧部分还未取完,左侧已经越界
			arr[k] = aux[j - l];
			j++;
		} else if(j > r) {					    // 只取左边
			arr[k] = aux[i -l];
			i++;
		} else if (aux[i - l] < aux[j - l]){	// l-r 存放较小的元素,从两块中取
			arr[k] = aux[i - l];
			i++;
		} else {
			arr[k] = aux[j - l];
			j++;
		}
	}
}


// 递归使用归并排序,对arr[l...r]的范围进行排序
template<typename T>
void __mergeSort(T arr[], int l, int r){
	/*	
	if(l >= r){
		return;
	}
	*/
	
	if(r - l <= 15){
		insertionSort2(arr,l,r);
		return;
	}

	int mid = l / 2 + r / 2;
	__mergeSort(arr, l ,mid);
	__mergeSort(arr, mid + 1, r);
	if (arr[mid] > arr[mid + 1])	// 只有左边最大值比右边最小值大,才需要归并
		__merge(arr, l, mid, r);

}

// 自顶向下
template<typename T>
void mergeSort(T arr[], int n){
	__mergeSort(arr, 0, n -1);
}

// Merge Sort Bottom 自底向上 可以对链表进行排序 
template<typename T>
void mergeBU(T arr[], int n){
	for( int sz = 1; sz <= n ; sz += sz )
		for( int i = 0 ; i < n - sz ; i += sz+sz )
			if( arr[i+sz-1] > arr[i+sz] )
				__merge(arr, i, i+sz-1, min(i+sz+sz-1,n-1) );
}

// Merge Sort Bottom 自底向上 
template<typename T>
void mergeBU2(T arr[], int n){
	for(int i = 0;i < n;i < 16)
		insertionSort(arr, i, min(i + 15, n -1));
	for( int sz = 16; sz <= n ; sz += sz )
		for( int i = 0 ; i < n - sz ; i += sz+sz )
			if( arr[i+sz-1] > arr[i+sz] )
				__merge(arr, i, i+sz-1, min(i+sz+sz-1,n-1) );
}
